package cn.xkai.exercise.a;

import com.google.gson.Gson;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @description: 合并区间
 * 自己的思路：排序后，未完成
 * 借鉴的思路：先进行升序排列，直到判断第二位比后面大，添加到list，然后输出list集合
 * @author: kaixiang
 * @date: 2022-06-19
 **/
public class Solution4 {
    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) return intervals;
        //1、对二维数组按照第一列升序排序
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        //2、进行合并数组
        List<int[]> list = new ArrayList<>();
        //临时空间，1 判断是否需要合并集合，2 是否放入结果集
        int[] term = intervals[0];
        for (int i = 1; i < intervals.length; i++) {
            if (term[1] >= intervals[i][0]) {
                term[1] = Math.max(term[1], intervals[i][1]);
            } else {
                list.add(term);
                term = intervals[i];
            }
        }
        list.add(term);
        return list.toArray(new int[list.size()][2]);
    }

    public static void main(String[] args) {
        int[] interval1 = new int[]{2, 3};
        int[] interval2 = new int[]{4, 6};
        int[] interval3 = new int[]{8, 10};
        int[] interval4 = new int[]{7, 18};
        int[][] intervals = new int[][]{interval1, interval2, interval3, interval4};
        Solution4 solution4 = new Solution4();
        System.out.println(new Gson().toJson(solution4.merge(intervals)));
    }
}
